package bTree.LeetCode;

import java.util.Random;

public class 排序数组 {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        if(left>=right){
            return;
        }
        int slow=left,medium=left,fast=right;
        Random random=new Random();
        int point=nums[left+random.nextInt(right-left+1)];
        while (medium<=fast){
            if(nums[medium]>point){
                swap(nums,medium,fast);
                fast--;
            } else if (nums[medium]<point) {
                swap(nums,medium,slow);
                slow++;
                medium++;
            }else {
                medium++;
            }
        }
        quickSort(nums,left,slow-1);
        quickSort(nums,medium,right);
    }
    private void swap(int[]nums,int l,int r){
        int temp=nums[l];
        nums[l]=nums[r];
        nums[r]=temp;
    }
}